/**
 * 简化路径
 *
 * 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。
 * 在 Unix 风格的文件系统中规则如下：
 * 一个点 '.' 表示当前目录本身。
 * 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
 * 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
 * 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。
 * 返回的 简化路径 必须遵循下述格式：
 * 始终以斜杠 '/' 开头。
 * 两个目录名之间必须只有一个斜杠 '/' 。
 * 最后一个目录名（如果存在）不能 以 '/' 结尾。
 * 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
 * 返回简化后得到的 规范路径 。
 *
 * 示例 1：
 * 输入：path = "/home/"
 * 输出："/home"
 * 解释：
 * 应删除尾随斜杠。
 *
 * 示例 2：
 * 输入：path = "/home//foo/"
 * 输出："/home/foo"
 * 解释：
 * 多个连续的斜杠被单个斜杠替换。
 *
 * 示例 3：
 * 输入：path = "/home/user/Documents/../Pictures"
 * 输出："/home/user/Pictures"
 * 解释：
 * 两个点 ".." 表示上一级目录（父目录）。
 *
 * 示例 4：
 * 输入：path = "/../"
 * 输出："/"
 * 解释：
 * 不可能从根目录上升一级目录。
 *
 * 示例 5：
 * 输入：path = "/.../a/../b/c/../d/./"
 * 输出："/.../b/d"
 * 解释：
 * "..." 在这个问题中是一个合法的目录名。
 *
 * 提示：
 * 1 <= path.length <= 3000
 * path 由英文字母，数字，'.'，'/' 或 '_' 组成。
 * path 是一个有效的 Unix 风格绝对路径。
 */

/**
 * 方法一 (错误) :
 * 我们从后向前遍历
 * . 和 字母都是很好去写的, 我们这里的处理方法是遇到 . 就直接忽略, 在之前的 / 中解决 . 的问题
 * 字母的话直接拼接就好, 也是一样, 所有的问题都在 / 中解决, 下面我们来特别关注 /
 * 就看一个 '/'
 *    ////    ->    /
 *    ./      ->   可以直接忽略
 *    ../     ->   返回上一级  ->  怎么返回呢 ?   --> 举个例子 :  /.../cc/ab/../  ->  /.../cc/
 *                                                 就是去掉一个(或多个) / 然后再去掉连着的字母, 或者点
 *    ...     ->   当做普通 字母
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
        test.simplifyPath("/a/./b/../../c/");
    }

    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    // 这种方法是错的, 上面有一个例子 "/a/./b/../../c/", 要是我们遇到这种情况
    // 直接就会全局崩掉, 因为我们是从后向前走的, 所以 ../ 直接就会将前面的 ../
    // 也给忽略, 但是因为正常情况下是从前向后走的, 所以这是不能忽略的, 而是叠加的
    // 所以我们的这个思路是存在问题的 !!!!!!!!!!!!!!!
    public String simplifyPath1(String path) {

        // 字符串拼接函数
        StringBuffer ret = new StringBuffer();

        // 长度
        int n = path.length();

        // 倒序, 这里我们不处理 i, 在每种情况下去处理 i 的变化
        for (int i = n - 1; i >= 0; ) {

            // 这个位置的字符
            char ch = path.charAt(i);

            if (ch == '/') {

                // 要是 为 /
                // ***********************************
                // 整个核心步骤

                int len = getSwayRodLen(path, i);

                if (len >= 2) {

                    // 要是 //// 这样 就直接 -> /
                    ret.append('/');

                    i -= len;

                } else {

                    // 这有一个 / 单独出来
                    // "/"

                    // 我们吸纳减一, 后面在长度的时候就不用 i - 1
                    i--;

                    // 这里还要考虑下 -- ,之后是否会越界
                    if (i >= 0) {

                        int k = getPointLen(path, i);

                        if (k == 1) {

                            // "./"
                            // 跳过
                            i--;

                        } else if (k == 2) {

                            // "../"

                            i -= 2;

                            // 我能跳一定是可以跳的
                            // 这里不用特判, 因为一定成立 i >= 0
                            int m = getSwayRodLen(path, i);

                            // 跳过 / 或者 /////
                            i -= m;

                            // 判断一下是不是跳过的是第一个 /
                            // 要是的话要加上
                            if (i < 0) {
                                ret.append('/');
                            } else {

                                // 不是的, 继续跳有效路径
                                // 这里有两种情况, 一种是 字母, 一一种是 ...
                                int l1 = getCharLen(path, i);
                                int l2 = getPointLen(path, i);
                                i -= l1 + l2;
                            }


                        } else {

                            // 这里有两种情况, 就是 m == 0 或者 m >= 3
                            // 好在可以一起解决

                            // 别忘了 这是正常的情况, 我们先把 刚才 减去 / 加上
                            ret.append('/');

                            // 这里要是 有 ... , 就全加上
                            while (k > 0) {
                                ret.append('.');
                                k--;
                                i--;
                            }
                        }


                    } else {

                        // 要是已经 到第一个 /
                        // 加入就可以了
                        // 开头还是要用它的
                        ret.append('/');

                    }

                }

            } else if (ch == '.') {

                // 为 .
                // ***********************

                // 这里我们只要处理 下 ... 为 特殊路径的情况, 其他的直接跳过就好了
                // 其实也只剩下 ... 的情况了, 因为 别的情况都已经处理掉了

                int len = getPointLen(path, i);

                if (len >= 3) {

                    // 这里我们将 ... 全都加入 结果集中
                    while (len > 0) {
                        ret.append('.');
                        len--;
                        i--;
                    }

                } else {

                    // 这种情况理论是不会出现的, 但是我们也判断一下
                    i -= len;

                }

            } else {

                // 字母
                // ***********************

                ret.append(path.charAt(i));
                i--;

            }
        }

        // 这里我们的第一个 / 是处理不掉的, 所以我们要在最后的时候处理下, 当然, 只有一个 / 的情况肯定要保留
        if (ret.charAt(0) == '/' && ret.length() > 1) {
            ret.deleteCharAt(0);
        }

        return ret.reverse().toString();
    }

    // 求连着的 .
    private int getPointLen(String path, int i) {
        int len = 0;
        for (; i >= 0; i--) {
            if (path.charAt(i) == '.') {
                len++;
            } else {
                break;
            }
        }
        return len;
    }

    // 求连着的 /
    private int getSwayRodLen(String path, int i) {
        int len = 0;
        for (; i >= 0; i--) {
            if (path.charAt(i) == '/') {
                len++;
            } else {
                break;
            }
        }
        return len;
    }

    // 求连着的 字母
    private int getCharLen (String path, int i) {
        int len = 0;
        for (; i >= 0; i--) {
            if ((path.charAt(i) >= 'a' && path.charAt(i) <= 'z')
                    || (path.charAt(i) >= 'A' && path.charAt(i) <= 'Z')) {
                len++;
            } else {
                break;
            }
        }
        return len;
    }

    public String simplifyPath(String path) {
        path += "/";
        char[] stack = new char[path.length()];
        int pos = -1;
        char[] arr = path.toCharArray();
        for(int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if(pos == -1) {
                stack[++pos] = c;
            } else {
                if(c == '/') {
                    if(stack[pos] == '/') {
                        pos --;
                    } else if(stack[pos] == '.') {
                        int dot_cnt = 0;
                        int t_pos = pos;
                        while(t_pos>=0 && stack[t_pos] != '/') {
                            if(stack[t_pos] == '.') {
                                dot_cnt++;
                            } else {
                                dot_cnt = 0;
                                break;
                            }
                            t_pos--;
                        }
                        if(dot_cnt> 0 && dot_cnt <= 2) {
                            int level = dot_cnt / 2 + 1;
                            while(pos >=0 && level > 0) {
                                if(stack[pos--] == '/') {
                                    level--;
                                }
                            }
                        }

                    }
                    stack[++pos] = c;
                } else {
                    stack[++pos] = c;
                }
            }
        }
        if(pos > 1 && stack[pos] == '/') {
            pos--;
        }
        return new String(stack, 0, pos + 1);
    }
}